package com.gaofeng.algo.kt

import java.util.*
import kotlin.math.sqrt

fun main() {

}

private fun twoSum(numbers: IntArray, target: Int): IntArray {
    var lo = 0
    var hi: Int = numbers.size - 1
    while (lo < hi) {
        val sum = numbers[lo] + numbers[hi]
        when {
            sum > target -> {
                hi--
            }
            sum < target -> {
                lo++
            }
            else -> {
                return intArrayOf(lo + 1, hi + 1)
            }
        }
    }
    return intArrayOf(-1, -1)
}

private fun minWindow2(s: String, t: String) {
    val flags = BooleanArray(128)
    val chars = IntArray(128)
    for (i in t.indices) {
    }
}

fun minWindow(s: String, t: String): String? {
    val chars = IntArray(128)
    val flags = BooleanArray(128)
    //flags判断是否包含t中的元素
    //chars数组记录了t中元素的个数
    for (i in t.indices) {
        flags[t[i].toInt()] = true
        ++chars[t[i].toInt()]
    }
    var cnt = 0
    var l = 0
    var min_l = 0
    var min_size = s.length + 1
    for (r in s.indices) {
        //移动右指针的过程中,如果包含t中的元素
        if (flags[s[r].toInt()]) {
            //将t中的元素个数自减,然后统计数量+1
            if (--chars[s[r].toInt()] >= 0) {
                ++cnt
            }
            //当统计的数量等于t中元素的个数时,说明包含了t,此时移动左指针,缩减空间
            while (cnt == t.length) {
                if (r - l + 1 < min_size) {
                    min_l = l
                    min_size = r - l + 1
                }
                //如果包含左指针,并且左指针自增之后大于0,说明当前左指针的元素时唯一的一个
                //此时将cnt自减,那么就不会再满足循环条件
                if (flags[s[l].toInt()] && ++chars[s[l].toInt()] > 0) {
                    --cnt
                }
                //移动左指针
                ++l
            }
        }
    }
    //最小size默认设置为s的长度+1,用于判断是否包含t
    return if (min_size > s.length) "" else s.substring(min_l, min_l + min_size)
}

fun judgeSquareSum(c: Int): Boolean {
    var start = 0
    var end = sqrt(c.toDouble()).toInt()
    while (start <= end) {
        val sum = start * start + end * end
        when {
            sum == c -> {
                return true
            }
            sum < c -> {
                start++
            }
            else -> {
                end--
            }
        }
    }
    return false
}


fun validPalindrome(s: String): Boolean {
    var start = 0
    var end = s.length - 1
    while (start < end) {
        if (s[start] == s[end]) {
            start++
            end--
        } else {
            var flag1 = true
            var flag2 = true
            var i = start
            var j = end - 1
            while (i < j) {
                if (s[i] != s[j]) {
                    flag1 = false
                    break
                }
                i++
                j--
            }

            var k = start + 1
            var l = end
            while (k < l) {
                if (s[k] != s[l]) {
                    flag2 = false
                    break
                }
                k++
                l--
            }
            return flag1 || flag2
        }
    }
    return true
}

fun findLongestWord(s: String, d: List<String>): String? {
    Collections.sort(
        d
    ) { o1, o2 -> if (o1.length != o2.length) o2.length - o1.length else o1.compareTo(o2) }
    for (x in d) {
        if (isSubSequence(x, s)) {
            return x
        }
    }
    return ""
}

fun isSubSequence(x: String, y: String): Boolean {
    var j = 0
    var i = 0
    while (i < y.length && j < x.length) {
        if (y[i] == x[j]) {
            j++
        }
        i++
    }
    return j == x.length
}